#include <iostream>
using namespace std;
#define maxsize 1000
typedef struct Bitnode
{
    char data;
    struct Bitnode *lchild, *rchild;
    int ltag, rtag;//tag=0,指向孩子；tag=1，指向前驱后继
}BitNode,*Bittree;//线索二叉树

Bittree dlrbitree()//递归法先序建立二叉树，空指针@拓展
{
    Bittree T;
    char ch;
    //cin >> ch;
    scanf("%c", &ch);
    if(ch=='@')
        T = NULL;
    else
    {
        T = new BitNode;
        T->data = ch;
        T->lchild = dlrbitree();
        T->rchild = dlrbitree();
    }
    return T;
}

Bittree pre = NULL;
void inthread(Bittree p)//中序线索化二叉树（不带头节点，p为根）
{
    if(p!=NULL)//递归结束条件，p为工作指针
    {
        inthread(p->lchild);//一直到没有左子树，即中序
        if(p->lchild==NULL)//p没有左孩子，左指针指向前驱pre
        {
            p->ltag = 1;
            p->lchild = pre;
        }
        else
            p->ltag = 0;
        if(pre->rchild==NULL)//pre没有右孩子，右指针指向后继p
        {
            pre->rtag = 1;
            pre->rchild = p;
        }
        else
            pre->rtag = 0;
        pre = p;//前驱跟上工作指针p
        inthread(p->rchild);
    }
}//中序线索化结束时pre在最后一个结点

void inthrt(Bittree &thrt,Bittree T)//中序线索化二叉树（带头节点，T为根）
{
    thrt = new BitNode;//头结点
    thrt->ltag = 0;//头结点左孩子指向根结点
    thrt->rtag = 1;//头结点右孩子指向最后一个，最后一个结点右孩子指向头结点
    thrt->rchild = thrt;
    if(T==NULL)//空树
        thrt->lchild = thrt;
    else//非空树
    {
        thrt->lchild = T;//头结点左孩子指向根
        pre = thrt;//初始前驱为头节点
        inthread(T);//中序线索化二叉树，中序线索化结束时pre在最后一个结点
        pre->rchild = thrt;//最后一个结点右孩子指向头结点
        pre->rtag = 1;
        thrt->rchild = pre;//头结点右孩子指向最后一个结点
    }
}
/*
void output(Bittree T)//递归输出树
{
    if(T)
    {
        output(T->lchild);//先左孩子
        cout << T->data;//中序
        output(T->rchild);//后右孩子
    }
}*/
void ldrpopbit(Bittree thrt)//中序遍历中序线索二叉树（带头节点）
{
    Bittree p;
    p=thrt->lchild;
    while(p!=thrt)//树不为空
    {
        while(p->ltag==0)//找到没有左孩子的结点
        {
            p = p->lchild;
        }
        cout << p->data;
        while((p->rtag==1)&&(p->rchild!=thrt))//顺着后继输出直到找到有右孩子的点
        {
            p = p->rchild;
            cout << p->data;
        }
        p = p->rchild;//p移动到右孩子上
    }
}


int main()
{
    Bittree thrt,T;
    T=dlrbitree();
    inthrt(thrt, T);
    ldrpopbit(thrt);
    return 0;
}
